package fun.ticsmyc.dataStructure;

import fun.ticsmyc.tools.TreeNode;
import org.junit.Test;

import java.util.*;

/**
 * @author Ticsmyc
 * @package fun.ticsmyc.dataStructure
 * @date 2020-02-21 9:06
 */
public class 判断二叉树的类型 {
    @Test
    public void test() {
        TreeNode head = new TreeNode(5);
        head.left = new TreeNode(3);
        head.right = new TreeNode(8);
        head.left.left = new TreeNode(2);
        head.left.right = new TreeNode(4);
//        head.left.left.left = new TreeNode(1);
//        //head.left.left.left.left = new TreeNode(111);
//        head.right.left = new TreeNode(7);
//        head.right.left.left = new TreeNode(6);
//        head.right.right = new TreeNode(10);
//        head.right.right.left = new TreeNode(9);
//        head.right.right.right = new TreeNode(11);

        System.out.println("平衡二叉树: ");
        判断平衡二叉树 a = new 判断平衡二叉树();
        System.out.println(a.judge(head));
        System.out.println();

        System.out.println("二叉搜索树: ");
        判断二叉搜索树 b = new 判断二叉搜索树();
        System.out.println(b.judge2(head));
        System.out.println();

        System.out.println("完全二叉树: ");
        判断完全二叉树 c = new 判断完全二叉树();
        System.out.println(c.judge(head));
        System.out.println();
    }
}

class 判断完全二叉树 {
    public boolean judge(TreeNode TreeNode) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        boolean single = false;
        queue.add(TreeNode);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if ((single && (cur.left != null || cur.right != null)) || (cur.left == null && cur.right != null)) {
                return false;
            }
            if (cur.left != null) {
                queue.add(cur.left);
            }
            if (cur.right != null) {

                queue.add(cur.right);
            } else {
                single = true;
            }
        }
        return true;
    }

    public boolean judge2(TreeNode treeNode) {
        Deque<TreeNode> queue = new LinkedList<>();
        queue.add(treeNode);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                queue.add(cur.left);
                queue.add(cur.right);
            } else {
                break;
            }
        }
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                return false;
            }
        }
        return true;
    }
}

class 判断平衡二叉树 {

    public boolean judge(TreeNode root) {
        return root == null || Math.abs(deep(root.left) - deep(root.right)) < 2 && judge(root.left) && judge(root.right);
    }

    public int deep(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(deep(root.left), deep(root.right));
    }

}

class 判断二叉搜索树 {
    /**
     * 非递归中序 + 判断是否递增
     *
     * @param root
     * @return
     */
    public boolean judge1(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        int last = 0;
        TreeNode TreeNode = root;
        boolean first = true;
        while (TreeNode != null || !stack.isEmpty()) {
            if (TreeNode != null) {
                stack.push(TreeNode);
                TreeNode = TreeNode.left;
            } else {
                TreeNode = stack.pop();
                if (!first) {
                    if (TreeNode.val <= last) {
                        return false;
                    }
                }
                first = false;
                last = TreeNode.val;
                TreeNode = TreeNode.right;
            }
        }
        return true;
    }

    /**
     * 递归中序+判断递增
     */
    private int last = 0;
    private boolean res = true;
    private boolean first = true;

    public boolean judge2(TreeNode root) {
        trace(root);
        return res;

    }

    private void trace(TreeNode root) {
        if (root == null || res == false) {
            return;
        }

        trace(root.left);

        if (!first) {
            if (root.val <= last) {
                res = false;
                return;
            }
        }
        last = root.val;
        first = false;
        trace(root.right);
    }

    /**
     * 优雅的递归判断
     */
    public boolean isValidBST(TreeNode root) {
        return judge(root, null, null);
    }

    public boolean judge(TreeNode root, TreeNode min, TreeNode max) {
        if (root == null) return true;
        if (min != null && root.val <= min.val) return false;
        if (max != null && root.val >= max.val) return false;
        return judge(root.left, min, root) && judge(root.right, root, max);
    }

}

